'''
https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/description/
'''
from typing import List

class UnionFind:
    def __init__(self, n):
        self.father = [i for i in range(n)]
    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]
    def is_same_set(self, i, j):
        return self.find(i) == self.find(j)
    def union(self, i, j):
        self.father[self.find(i)] = self.find(j)


class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # 对边按权值从小到大排序
        edgeList.sort(key=lambda x: x[2])
        # questions = [[i, u, v, limit] for i, u, v, limit in enumerate(queries)]
        questions = [[i, *q] for i, q in enumerate(queries)]
        questions.sort(key=lambda x: x[3])
        # print(questions)

        mst = []
        uf = UnionFind(n)
        t = 0
        ans = [False] * len(queries)
        for i, from_node, to_node, limit in questions:
            while t < len(edgeList):
                u, v, w = edgeList[t]
                if w >= limit:
                    break
                if not uf.is_same_set(u, v):
                    uf.union(u, v)
                    mst.append((u, v, w))
                    if len(mst) == n - 1:
                        break
                t += 1
            ans[i] = uf.is_same_set(from_node, to_node)
        return ans